题目

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

解答

思路

对于无序的数组，解决两数之和问题，可以使用哈希表。

而本题是有序数组，可以优化空间复杂度，利用有序的性质，使用对撞指针寻找符合条件的数对。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                return {nums[l], nums[r]};
            }
            else if(sum < target){ // 当前和小了
                l ++; // 左指针右移
            }
            else{ // 当前和大了
                r --; // 右指针左移
            }
        }
        return {-1, -1};
    }
};

复杂度

  • 时间复杂度 O(N)
  • 空间复杂度 O(1)